package com.kaifamiao.arrays;

import java.util.Arrays;

// 插入排序(insertion sort): 一般也被称为直接插入排序
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = { 10, 2, 9, 3, 6, 7, 8, 4, 5, 1 };

        for (int i = 1; i < arr.length; i++) {
            System.out.println( i );
            // 设前i个值是有顺序的序列，
            // 则需要确定当前的值(arr[i])应该插入到之前序列的哪个位置
            for( int j = i; j > 0 ; j--){
                // 若当前位置的值比前一个值小则进行交换
                if( arr[j] < arr[j-1] ) {
                    arr[j] ^= arr[j-1];
                    arr[j-1] ^= arr[j];
                    arr[j] ^= arr[j-1];
                }
                System.out.println( Arrays.toString( arr ) );
            }
        }
    }
}
